// 快排
func sortArray(nums []int) []int {
    dfs(nums, 0, len(nums) - 1)
    return nums
}

func dfs(nums []int, lo int, hi int) {
    if lo >= hi {
        return
    }
    index := partition(nums, lo, hi)

    dfs(nums, lo, index - 1)
    dfs(nums, index + 1, hi)
}

// 二分切分
func partition(nums []int, lo int, hi int) int {
    i := rand.Intn(hi - lo + 1) + lo
    nums[i], nums[hi] = nums[hi], nums[i]
    pivot := nums[hi]
    less, great := lo, lo
    for ; great <= hi - 1; great++ {
        if nums[great] < pivot {
            nums[less], nums[great] = nums[great], nums[less]
            less++
        }
    }
    nums[less], nums[hi] = nums[hi], nums[less]
    return less
}